home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 3833 < prev    next >
Encoding:
Text File  |  1996-08-05  |  2.5 KB  |  57 lines
  1. Path: longwood.cs.ucf.edu!not-for-mail
  2. From: schnitzi@longwood.cs.ucf.edu (Mark Schnitzius)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: Sorting large files
  5. Date: 31 Jan 1996 08:46:10 -0500
  6. Organization: University of Central Florida
  7. Message-ID: <4enrr2$ofn@longwood.cs.ucf.edu>
  8. References: <4e8j9b$cuf@longwood.cs.ucf.edu> <4elhik$cpq@ibm32.perftech.com>
  9. NNTP-Posting-Host: longwood.cs.ucf.edu
  10.  
  11. murf@perftech.com (John Murphy) writes:
  12.  
  13. >In article <4e8j9b$cuf@longwood.cs.ucf.edu>, schnitzi@longwood.cs.ucf.edu 
  14. >says...
  15. >>
  16. >>There was some discussion here a little while
  17. >>back on how to sort the lines in a large file
  18. >>without having to have a huge character array.
  19. >>I suggested using ftell and fseek to hunt down
  20. >>the particular lines you are comparing.  
  21.  
  22. >Who says computer people don't have a sense of humor?!
  23.  
  24. >Least any neophytes miss the joke and take this as a serious solution to the
  25. >sorting problem, perhaps we should point out that while this code will
  26. >compile and run and even (eventually) sort a file, it's practical use will
  27. >be limited by the MTBF of your equipment and/or your life expectancy ---
  28. >it's SLOOOW!  Any file I/O operation is time consuming, and depending on the
  29. >file system, random file I/O can be VERY time consuming; with MS-DOS, for
  30. >instance, reading a large file backwards is an N-squared operation.
  31.  
  32. It was really only half tongue-in-cheek.  I would compare it to
  33. using an insertion sort -- it's much slower than, say, quicksort,
  34. but still has its practical uses.  Namely, it is much, much easier
  35. to code than a merge sort that creates intermediate files.  If I
  36. had to sort a large file in a hurry and didn't have access to any
  37. system sort routines, I would use the fseek/ftell trick.
  38.  
  39. This is not to say that it is any substitute for doing a multi-file
  40. merge sort if speed is an issue.  Others have pointed out other
  41. practical limitations to it as well; such as the fact that it won't
  42. work for a million-line file.
  43.  
  44. >As a sanity check on the practicality of this method of sorting, try sorting
  45. >a 20,000 byte file; that's a file that would require the same amount of
  46. >memory as the array of 5000 longs.  On one of my systems, using this code to
  47. >sort a file of 250 80 bytes records took 17:30 minutes; sorting the same
  48. >file with MS-DOS SORT (a very slow sort program) took 0.8 seconds.
  49.  
  50. Interesting!
  51.  
  52.  
  53.  
  54. _____________________________________________________________
  55. mark schnitzius - - - - - - - - - - - - - schnitzi@mentos.com
  56. - - - -<a href="http://east.isx.com/~schnitzi/">me</a>- - - -
  57.